Cheat sheet of stuff I always forget.md (2618B)
1 +++ 2 title = 'Cheat sheet of stuff I always forget' 3 +++ 4 # Cheat sheet of stuff I always forget 5 γ = 0.5772 6 7 Harary: 8 9 - forming a harary graph Hk,n: 10 - if k is odd and n is odd — make each vertex adjacent to (k-1)/2. then index nodes by integers mod n, and connect node to integer+(n-1)/2 for 0≤integer≤(n-1)/2 11 - yes, one node will have an even degree — the one labelled (n-1)/2 12 13 ranked embedding — choose an arbitrary vertex u, rank other vertices by distance from u, put vertices on separate lines based on ranking 14 15 Euler’s formula for planar graphs: 16 17 - n-m+r=2 18 - n vertices, m edges, r regions 19 20 condition for planar graph: m ≤ 3v-6 21 22 a graph is a tree if: 23 24 - n vertices, n-1 edges 25 - there is exactly one path between any two vertices 26 - every edge is a cut edge (a loop is never a cut edge, a cycle has no cut edges) 27 28 ε(u) — eccentricity. longest shortest path from u and to any other vertices 29 rad(G) — radius. minimum eccentricity 30 31 clustering — when many neighbours of vertex are also each other’s neighbours 32 defined by: 33  34 where mv is number of links between neighbours of v. 35 36 network transitivity τ(G) = nΔ(G) / ntriple(G) 37 38 vertex centrality of u cE(u) = 1 / ε(u) 39 betweenness centrality of u cB(u) = sum |S(x,u,y)| / |S(x,y)| for x≠u≠y 40 41 - S(x,y) — set of shortest paths between x and y 42 - S(x,u,y) — shortest paths passing through u, S(x,u,y) ⊆ S(x,y) 43 44 closeness of u cc(u) = 1 / (sum d(u,v) for all v in G) 45 46 **Random graphs** 47 ER(n,p): 48 49 - n vertices, edge exists with probability p 50 - expected clustering coefficient is p 51 - phase transition around p=1/n — a gigantic connected component appears 52 53  54 55 WS(n,k,p): 56 57 - construct Hn,k , replace edges with probability p 58 - “small world” — high clustering coefficients 59 - CC(G) ≈ 0.75 for G ∈ WS(n,k,0) 60 61 BA(n, n0, m): 62 63 - n vertices, m edges 64 - preferential attachment (a new node is more likely to connect to nodes with high degrees) leads to hubs 65 - P(v is linked to u) =  66 67 **Communities** 68 69 proximity prestige: (fraction of vertices that can reach v) / (average distance of those vertices to v) 70 71 a signed graph (edges labelled +/-) is balanced if all its cycles are positive (product of edge labels is positive) 72 73 signed graph is balanced iff its vertices can be partitioned into two disjoint subsets such that: 74 75 - each negative edge joins the subsets, and 76 - each positive edge joins vertices in the same subset 77 78 affiliation networks are naturally bipartite, with two sets (Va actors, Ve events)